var sortArray = function (nums) {
  // console.time("希尔排序耗时");
  // const N = nums.length;
  // let h = 1;
  // while (h < N / 3) {
  //   h = 3 * h + 1;
  // }

  // while (h >= 1) {
  //   for (let i = h; i < N; i++) {
  //     for (let j = i; j >= h && nums[j] < nums[j - h]; j -= h) {
  //       swap(nums, j, j - h);
  //     }
  //   }
  //   h = Math.floor(h / 3)
  // }
  // console.timeEnd("希尔排序耗时");
  // return nums;
  const N = nums.length;
  for (let gap = N / 2; gap > 0; gap = Math.floor(gap/2)) {
    for (let i = gap; i < N; i++) {
      let temp = nums[i];
      let j = i;
      while(j >= gap && nums[j - gap] > temp){
        nums[j] = nums[j - gap];
        j -= gap;
      }
      nums[j] = temp;
    }
  }
  return nums;
};

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

let arr = sortArray([6, 9, 0, 4, 8, 3, 2, 7, 1, 5]);
console.log(arr);
